The present invention generally relates to a processing system of the type including a plurality of processors coupled together on a shared bus, wherein the processors are arranged for executing program instructions from non-critical sections and at least one critical section and wherein exclusive execution of a critical section by one processor at a time is required. The present invention more particularly relates to such a processing system which is competitive coordinated and which is arranged to permit exclusive execution of a critical section by a processor without locking out the other processors from the shared bus for executing program instructions whose operands are not used by the instructions in the critical section.
Multiprocessor systems generally utilize one of two different types of coordination for permitting one processor at a time to execute a critical section. These types of coordination are referred to in the art as cooperative and competitive coordination.
In cooperative coordination, the processors are required to follow a set of protocols. The protocols typically require each processor to notify the other processors before and after the execution of a critical section. This is accomplished by busy-waiting, wherein each processor wishing to enter a critical section repeatedly tests the value of a variable associated with the critical section in a loop for an available value indicating that no other processor is currently executing the critical section. When the variable has the available value, the processor which is first to execute a read-modify-write instruction for atomically reading the available value and immediately writing the busy value of the variable enters the critical section, thereby preventing the other processors from reading the available value to preclude the other processors from entering the critical section. After completing the critical section, the processor then exits the critical section by writing the available value to permit another processor to acquire the variable in the same manner as described above.
Cooperative coordination works only if all processors involved strictly follow the protocol. A malicious or inadvertent violation of the protocol will result in improper functioning of the processing system. Hence, the usefulness of cooperative coordination is limited to trusting environments, such as within a processing system executing a single parallel program which has been written with extreme care.
In competitive coordination, there is no prearranged protocol among the processors. Competitive coordination is thus required in situations where it is difficult or impractical to define the protocols necessary for cooperative coordination. It is all generally easier to implement.
To support competitive coordination, shared bus architectures utilize bus locking. Before a processor enters a critical section, requiring the use of a shared resource, it locks the bus to be free to use the bus while the other processors are denied the use of the bus. The processor locking the bus maintains the locking of the bus until it completes the critical section or until there is a time out, in those systems which provide such a time out mechanism.
To provide bus locking, each processor of a competitive coordinated processing system includes a status register for storing a bit which controls the bus locking. Once this bit is set by a bus locking processor and the bus is acquired, the bus is not released until the bit in the register is cleared.
The bus locking approach has a detrimental side effect in that it effectively halts all but one processor from executing while the bus is locked. Hence, bus locking is useful only in situations where performance is of secondary concern or where the bus locking period is short.
As well known in the art, programs execute in one of the two modes: supervisor or user. Programs in the supervisor mode are permitted to execute any and all instructions the processors are capable of executing. In contrast, programs in the user mode are permitted to execute only a limited set of instructions. This distinction is based o the assumption that the programs run in the supervisor mode are written by the developer of the computer system, whereas the programs run in the user mode are written by users of the processing system. The restrictiveness in the user mode is for the purpose that a programming mistake made by one user does not affect other users.
Most processing system designs do not provide bus locking for the user mode programs. For those processing systems which do provide bus locking for the user mode programs, bus locking is made possible only with severe restrictions.
The present invention provides an improved competitive coordinated processing system which overcomes the deficiencies of such prior art competitive coordinating processing systems. The processing system of the present invention provides exclusive access to a critical section by a processor without locking out the other processors from the shared bus for executing instructions accessing data operands other than data operands used by the critical section. In addition, exclusive access to a critical section is provided to a processor by the present invention without the restrictions imposed by prior art systems such as the previously described bus locking system.